package class08

/*
	现有 n1 + n2 种面值的硬币，其中前n1种为普通币，可以取任意枚，后n2种为
	纪念币，每种最多只能取一枚，每种硬币有一个面值，问能用多少种方法拼出m的
	面值？

	算法流程：
		1. 问题拆解为两个子问题，并生成二维表
			1.a 单独使用普通币，凑成 0-money 有多少种方法
			1.b 单独使用纪念币，凑成 0-money 有多少种方法
		2. 和为money的方法数为，dp表一的i * dp表二的money-i 的方法数的总和
*/
func moneyWays(arbitrary , onlyOne []int, money int) int {
	if money < 0 {
		return 0
	}
	if len(onlyOne) == 0 && len(arbitrary) == 0 {
		if money == 0 {
			return 1
		}
		return 0
	}
	arbitraryDp := getArbitraryDp(arbitrary, money)
	onlyOneDp := getOnlyOneDp(onlyOne, money)
	if len(onlyOne) == 0 {
		return arbitraryDp[len(arbitrary)-1][money]
	}
	if len(arbitraryDp) == 0 {
		return onlyOneDp[len(onlyOne)-1][money]
	}
	var ans int
	for m:=0; m<= money; m++ {
		ans += arbitraryDp[len(arbitrary)-1][m] * onlyOneDp[len(onlyOne)-1][money-m]
	}
	ans += arbitraryDp[len(arbitrary)-1][money] + onlyOneDp[len(onlyOne)-1][money]
	// 0 + 0 +
	return ans
}


/*
	硬币可以重复取多次，凑成 money 的方法数

	1. 可能性分析
		递归函数 f(arbitrary, len(arbitrary)-1, money)
		0-len(arbitrary)-1 的硬币凑出刚好凑出 money 的方法数有多少种

	2. pd表拆解：

*/
func getArbitraryWays(arbitrary []int, money int) int {
	return getArbitraryProcess(arbitrary, len(arbitrary)-1, money)
}

func getArbitraryProcess(arbitrary []int, icon int, money int) int {
	if money == 0 {
		return 1
	}
	if icon < 0 {
		return 0
	}
	if money < 0 {
		return 0
	}
	// 10 元 硬币是 3元， 则可能出现 取一个3元，取2个三元 取3个三元
	// 10 / 3 = 3
	// 12 元 可以取四个三元 12/3 = 4
	// 当前最后一枚的硬币可以取多个，1个 到 小于等于 money 的可能性
	var ans int
	for i:=0; i<=money/arbitrary[icon]; i++ {
		ans += getArbitraryProcess(arbitrary, icon-1, money-(i*arbitrary[icon]))
	}
	return ans
}

/*
	采用填表的方式
*/
func getArbitraryDp(arbitrary []int, money int) [][]int {
	// 初始化 dp 表
	dp := make([][]int, len(arbitrary))
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, money+1)
		dp[i][0] = 1 // 初始化第一列
	}

	// 填写dp 表, 从依赖位置的关系推到，应该是从上往下，从左往右推导
	for i:=0; i<len(dp); i++ {
		for j:=1; j<len(dp[i]); j++ {
			// 1. 直接使用递归，赋值粘贴过来的写法
			var ans int
			for p:=0; p<=j/arbitrary[i]; p++ {
				if i-1 >= 0 && j-(p*arbitrary[i]) >= 0 {
					ans += dp[i-1][j-(p*arbitrary[i])]
				}
			}
			if i == 0 && j % arbitrary[i] == 0 {
				ans += 1
			}
			dp[i][j] = ans
			// 2. 基于表格规律做了优化，少去了遍历，直接从之前的结果获取答案
			//if i-1 >= 0 {
			//	dp[i][j] += dp[i-1][j]
			//}
			//if j-arbitrary[i] >= 0 {
			//	dp[i][j] += dp[i][j-arbitrary[i]]
			//}
		}
	}
	return dp
}

func getOnlyOneDp(onlyOne []int, money int) [][]int {
	dp := make([][]int, len(onlyOne))
	for i:=0; i<len(dp); i++ {
		dp[i] = make([]int, money+1)
		dp[i][0] = 1 // 初始化第一列
		if i == 0 { // 初始化第一行
			for j := 0 ; j <= money; j++ {
				if j == onlyOne[0] {
					dp[0][j] = 1
				}
			}
		}
	}

	for i:=0; i<len(dp); i++ {
		for j:=1; j<len(dp[i]); j++ {
			if i-1 >= 0 {
				dp[i][j] += dp[i-1][j]
				if j-onlyOne[i] >= 0 {
					dp[i][j] += dp[i-1][j-onlyOne[i]]
				}
			}
		}
	}
	return dp
}
